Exercise 9 (Homework 7).
(NP,
coNP,
DP,
Unique SAT)
\mathtt{Unique SAT}
The class \mathsf{DP} (for difference polynomial time) is defined as the set of languages L for which there are two languages L_1 \in \mathsf{NP}, L_2 \in \mathsf{coNP} such that L = L_1 \cap L_2. Notice that since \overline{L_2} \in \mathsf{NP}, L is the difference of two \mathsf{NP} sets (but do not confuse \mathsf{DP} with \mathsf{NP} \cap \mathsf{coNP}, which may seem superficially similar).
Consider the problem \mathtt{Unique SAT} on determining whether a Boolean formula has a unique satisfying assignment (or model) and show the following facts.
- \mathtt{Unique SAT} \in \mathsf{DP}.
- If \mathtt{Unique SAT} is in \mathsf{NP}, then \mathsf{NP} = \mathsf{coNP}.